import javafx.util.Pair;

import java.util.ArrayList;
import java.util.List;

/**
 * @author hewei
 * @version 1.0
 * @description: 1146. 快照数组
 * @date 2022/11/4 08:56
 */

public class SnapshotArray2 {

    int length;
    int curSnapId;
    List<Pair<Integer, Integer>>[] lists;

    public SnapshotArray2(int length) {
        curSnapId = -1;
        this.length = length;
        lists = new ArrayList[length];
        for (int i = 0; i < length; i++) {
            lists[i] = new ArrayList<>();
            lists[i].add(new Pair<>(curSnapId, 0));
        }
    }

    public void set(int index, int val) {
        List<Pair<Integer, Integer>> list = lists[index];
        lists[index].add(new Pair<>(curSnapId, val));
    }

    public int snap() {
        ++curSnapId;
        return curSnapId;
    }

    public int get(int index, int snap_id) {
        List<Pair<Integer, Integer>> list = lists[index];
        int l = 0;
        int r = list.size() - 1;
        while (l < r) {
            int mid = (r - l) / 2 + l + 1;
            Pair<Integer, Integer> pair = list.get(mid);
            Integer snap = pair.getKey();
            if (snap >= snap_id) {
                r = mid - 1;
            } else {
                l = mid;
            }
        }
        return list.get(l).getValue();
    }
}
